package features.advance.leetcode.array.easy;

import java.util.Arrays;

/**
 *
 *  453. 最小操作次数使数组元素相等
 *
 *  难度：简单
 * 给定一个长度为 n 的 非空 整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。
 *
 *
 *
 * 示例：
 *
 * 输入：
 * [1,2,3]
 * 输出：
 * 3
 * 解释：
 * 只需要3次操作（注意每次操作会增加两个元素的值）：
 * [1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
 *
 * @author LIN
 * @date 2021-05-11
 */
public class Solution453 {

    /**
     * 方法四：动态规划 【通过】
     * 算法
     *
     * 如果对数组进行排序得到有序数列 a，可以有效地简化问题。考虑有序数组 a，
     * 我们不考虑整个问题，而是将问题分解。假设，直到 i-1 位置的元素都已经相等，
     * 我们只需要考虑 i 位的元素，将差值 diff=a[i]-a[i-1] 加到总移动次数上，使得第 i 位也相等。moves=moves+diff。
     *
     * 但当我们想要继续这一步时，a[i] 之后的元素也会被增加 diff，亦即 a[j]=a[j]+diff，其中 j>i。
     *
     * 但当实现本方法时，我们不需要对这样的 a[j] 进行增加。相反，我们把 moves 的数量增加到当前元素（a[i]）中，
     * a'[i]=a[i]+moves。
     *
     * 简而言之，我们对数列进行排序，一直更新 moves 以使得
     *
     *
     * @param nums
     * @return
     */
    public int minMoves(int[] nums){
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        return 0;
    }


    public static void main(String[] args) {
        int[] nums = {1,2,3};

        Solution453 solution453 = new Solution453() {
            @Override
            public int minMoves(int[] nums) {
                /**
                 * 1,2,3,4
                 *
                 * 2,3,4,4
                 * 3,4,5,4
                 * 4,5,6,4
                 * 5,6,6,5
                 * 6,6,7,6
                 * 7,7,7,7
                 *
                 *
                 * 1,3,6
                 *
                 * 2,3,7
                 * 3,3,8
                 * 4,4,8
                 * 5,5,8
                 * 6,6,8
                 * 7,7,8
                 * 8,8,8
                 */
                if(nums == null || nums.length <= 1){
                    return 0;
                }
                int moves = 0;
                int min = nums[0];
                for (int i = 0; i < nums.length; i++) {
                    min = Math.min(min,nums[i]);
                    moves+=nums[i];
                }
                return moves - nums.length * min;
            }
        };
        int minMoves = solution453.minMoves(nums);
        System.out.println(minMoves);

    }
}

